[pja]

"Your 4096-bit RSA key is still 2^3072 times harder to break,"

No, because the difficulty of breaking RSA keys doesn't scale in the same way as symmetric encryption. Integer factorisation is much easier than a brute force search of the keyspace. A 1024-bit RSA key is believed to be roughly equivalent to an 80-bit symmetric key. A 3072 bit key is about as hard to brute force as an 128-bit symmetric key.

(Source: http://www.keylength.com/en/4/ )

[_phred]

Ah shoot, you're right. I'm an armchair crypto geek at best.

In any case, you can choose a public key exponent large enough to still make it a hard problem to crack in a reasonable amount of time. Barring some huge vulnerability in RSA that hasn't been discovered in 30 years of public scrutiny, of course.