I've been experimenting with GnuPG the last couple of days, trying out grander key sizes in different manners.

pub 4096R/6B0B9508 created: 2005-02-21 expires: never usage: CS
sub 4096g/9888FB03 created: 2005-02-21 expires: 2005-12-31 usage: E
sub 15360g/D31B780E created: 2005-04-20 expires: 2007-01-01 usage: E

The 15,360bit ElGamal encryption key took me about 20 hours to generate on an Intel Centrino 1400MHz. Encrypting a file take about 33 seconds on the same computer, and as gpg doesn't implement threads, 44 seconds on my Dual PIII 1000MHz as it only use one of the processors. In comparison a 4096bit ElGamal Encryption key take less then a second to encrypt to on the Centrino.

[kristianf@kfc003 gnupg-1.4.1]$ time gpg --homedir . -aer 0x6b0b9508 NEWS
29.94user 0.16system 0:32.98elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+466minor)pagefaults 0swaps

In conclusion, computers aren't heavily enough equipped to deal with 15,360bit encryption keys on a day to day basis in eg email conversations, but it should be considered if you need to keep something safe for a long time.

The reason I chose a 15,360bit key is that it is stated to be the equivalent of a 256bit symmetrical key, and hence the assymetrical part of the hybrid PKI system isn't the weakest link when using AES256 for the email content. This number was found at www.scramdisk.clara.net that state

Block Cipher Keylength	RSA Key Length	EC KeyLength
80	1024	160
112	2048	224
128	3072	256
192	7680	384
256	15360	512

"Maybe an interesting historic example on "key degradation" is the RSA
key the French banks use for their banking cards.

The system was designed in 1983 with a 320 bit RSA key. 320 bit seamed at
that time probably sufficient. (AFAIR even PGP 1 gave the option of 384
bit keys around 1990.) 8 years later in 1991 a 330 bit RSA keys has been
broken. And now factoring a 320 bit modulus takes on a cheap computer
about 1.5 days. They do not have the problem, that now old messages
can be decrypted, but they do have the problem of a widely installed
hardware base which handles only the 320 bit key. They are currently
going to 769 bit keys."

I sincerely hope they upgrade this in a timely manner, as 512bit RSA keys can be cracked in relatively short time today.