I did this after reading this fine best practices tutorial (for which I incidentally helped write a French translation). The gist of it is (1.) that you should set up GPG correctly to fetch keys from key servers (there's the parcimonie-related paranoia, but there's the very embarrassing fact that by default it seems that GPG never manages to talk to a key server); and (2.) that you should check that your key is secure by issuing the following and checking for things in red:
sudo apt-get install hopenpgp-tools # FINGERPRINT is the actual fingerprint, not a key ID hkt export-pubkeys "FINGERPRINT" | hokey lint
Generating a new key isn't especially hard but here is a reminder of what you have to do. You then have to re-sign the keys that you had signed with the old key, using the new one...
The formal transition statement signed by both keys is here, so that you can sign the new key if you had signed the old one.