Look at the time difference in decrypting the same message with my 4K and 16K keys. $ time gpg -d test4k.pgp You need a passphrase to unlock the secret key for user: "astor <astorx@tormail.org>" 4096-bit RSA key, ID CC925AD7, created 2012-12-19 (main key ID 706EE207) gpg: encrypted with 4096-bit RSA key, ID CC925AD7, created 2012-12-19    "astor <astorx@tormail.org>" Hello. real0m0.067s user0m0.060s sys0m0.004s $ time gpg -d test16k.pgp You need a passphrase to unlock the secret key for user: "astor <astorx@tormail.org>" 16384-bit RSA key, ID B4BB43D6, created 2013-05-08 (main key ID DED75362) gpg: encrypted with 16384-bit RSA key, ID B4BB43D6, created 2013-05-08    "astor <astorx@tormail.org>" Hello. real0m2.311s user0m2.300s sys0m0.000s The 16K key takes 34.5 times as long. At 2.3 seconds, there's a noticeable lag. That's one good reason not to use large keys if you're doing a lot of of crypto.