I used to love running on the beach. It was best in the winter, when the grey skies and cold air kept the beaches clear. < This is fine.
Run as far as you could, marking the perfect sand with the print of your shoes, and then turning, and following your prints home. < This, on the other hand, is clumsy. It's something I'm terrible for, cramming too many concepts into one sentence. It causes problems because in this sentence you start with "Run" but then you are "turning". To stick with the concept it should read: Run as far as you can, marking the perfect sand with the print of your shoes, then turn and follow your prints home. Conceptually I would tend to mark the experience out differently. The joy of marking the perfect sand with your prints is one experience, the experience of following the prints home is entirely another. Both are equally valid in mood terms, so I would actually make care to give them each a separate sentence.
Alone with the waves and the birds. < Not a sentence. Also maybe ocean instead of waves? I realise the sensory intention is auditory. Also you come back to talking about yourself in the head of the next paragraph whereas you've just been saying "you". This sentence is trying to bring it back to I, sort of, and also adding another leayer of experience into the first paragraph.
Ironically I think that this first paragraph probably needs revising and expanding. You have a soup of concepts, experiences etc. and they're all running over one another. Concision is not just about being efficient it's also about choosing the appropriate amount of words for your communication. I think that you have more to say to set up the final paragraph. Maybe, like a person who is running in the sand the prose should start a bit slow and then rev up to pace itself into a clean finish.
If so I would go for a structure like Paragraph One: experiential paragraph talking about tactile things like sand in your toes. Paragraph two: mix the tactile with the auditory go from the wind whipping over your skin to the sound of the waves to the cries of the birds. Paragraph three: Finally, visual mixed with memories. Racing the storm and seeing the black thunderheads and the soupy water of the ocean. Just a suggestion for expansion should that be your desire. Then at least you will be able to shoot for a concise style while at the same time parcelling up what you are trying to get across by sensory experience across nicely flowing paragraphs.
I remember running, and finding myself racing a storm. < I remember when I found myself racing a storm. We get that you are running.
The wind blew hard at my back, but I ran pace with it, so the air seemed still and silent. < The wind blew hard at my back, I ran pace with it to make the air still and silent. (Avoid things "seeming" like other things a strenuously as possible, language without seemed is almost always more evocative and dynamic. I am terrible for this and have had to close crop work for the word seems, seemed and seeming so many times.)
The world was quiet, and yet the storm was rolling in across the ocean. < Slight re-order: The storm was rolling across the ocean, yet my world was quiet. (Might use "calm" instead of quiet, but this is up to you. Just seems more lyrical to me.)
A violent storm, stacked black clouds walking on stick-legs of lightning. < This one was violent, stacked black clouds on stick legs of lightning. (Although I'm not sure about the lightning thing... but this is personal preference. To me it makes me think of the storm being a daddy long legs or something. Personally I experience ropes of lightning thrown from the bottom of black thunderheads but this is an entirely different image, so I guess it proves yours is evocative. Probably best to leave as is.)
And it was frightening, and yet I laughed with the joy of it. Of being young and fleet and running to beat the wind. < It was frightening, yet I laughed with the joy of it. I was young and fleet and could run to beat the wind.