When at the time of the last post, there still was debate on changing default algorithms still found in web archive which had rough consensus, the switch to RSA 2k keys as default has been performed.
Debian recommends using a 4k RSA key in their document about using subkeys and debian-keys readme file. A vast majority of about three quarters of keys in debian developers keyring is (still) DSA/Elgamal (counted by grepping through gpg's output).
In an interview with iX (a German computer sciences magazine, issue 11/2013, also available online for free), the inventor of PGP Phil Zimmermann recommends "at least 3k length when using RSA", although 1k keys are not broken yet. But they're "in reach of attackers rich in resources".
Right now both are said to be secure for adequate key sizes (4k recommended for RSA, 2k necessary for DSA2, otherwise you will use DSA1 which uses SHA-1).
For selecting a RSA key length, have a look at an overview on the actual strength provided by NIST (p. 64). It is easy to see that the strength does not linearly grow with the key length (and computing time), so double size does not mean "double security".
There was a problem with OpenSSL's DSA-implementation on Debian, but this was caused by using bad random data and could have happened with RSA, too.
Choosing Between RSA and DSA2
- RSA is more wide-spread, though not necessary in OpenPGP standard, all major implementations can deal with it; DSA2 not (yet)
- RSA offers much faster signature checking
- Smaller signatures, but they're small anyway; for e-mail and code signing probably negligible
- Faster key creation (can be relevant on low power and embedded devices like mobiles and routers)
- Slightly faster for signing
My own Decision
When recently creating a new OpenPGP key, I decided to go for 8k RSA for primary keys and 4k RSA as subkeys for daily use. RSA signatures are fast to verify anyway and the huge 8k signatures are only used for signing other keys, but 8k should be considered sufficient for a really long time. 4k is fine for a current subkey as it's cheap to revoke it without loosing all your signatures.
Creating that 8k key took about 20 minutes on my Core 2 Duo T9300, so take your time and do some work (for feeding the random source).