How to migrate my old PGP key to a more secure algorithm?

Solution 1:

There is no way to "upgrade" an OpenPGP key. You will have to create a new one, and you will lose your reputation in the web of trust.

Some people I met decided to stick with a RSA 1024 primary key, but use stronger subkeys instead (which is easily possible without losing your reputation in the web of trust), which comes with secure day-to-day use (for encryption/signing documents with your subkeys), but might enable attackers to add and revoke certifications, subkeys and UIDs.

Think about:

• Signing your new key with the old one, so others could follow the signatures
• Sending a key transition statement (seems down, alternative link on archive.org) to those that signed your old key; some of them might also sign your new one
• Getting your new key signed, i.e. go to key signing parties
• Revoking the old one after some time
• Using a seemingly unnecessary large key as primary key and smaller subkeys for day-to-day usage. You will never need the primary key for anything but signing other keys (which is rare) and others verifying your signatures (which is cheap anyway).