I tried my test of encrypting a ~20k message with a 4096 bit key on a ~150MHz Pentium. What takes 2 seconds on my fairly obsolete hardware, takes about 4 seconds on the even older Pentium. In other words, even using keys >4096 bits is practical.