To keep it short: I'm transitioning from my old 1024 DSA to a new 4096 RSA GPG key because Debian nowadays prefers stronger keys. Here is my transition document (which I shamelessly copied from zack).