I noticed the same decay. My penmanship was never good, and over the past few years it has gotten decidedly worse. I cringe now, when I have to fill out standard forms with a pen.
I keep a journal at my desk and I write in it faithfully. I highly recommend a Moleskine that suits your personal taste. I use them because the paper is very high quality, gel pens don't run and your average Bic won't suddenly refuse to write.
Log what you do, when you did it, how you felt about it, what you saw, memories from childhood that a certain smell provoked, or whatever suits your fancy. The point is, you need to remind your brain that forming words can be done with keystrokes or a pen. You can practice for a month on a white board and produce brilliant, legible scratch .. however easy come, easy go.
If you want to attain and keep any skill, you need to practice :)
Additionally, the journal makes for interesting reading later.