I have a very slow connection, and I need to use SSH on it. How can I increase "the speed"? I mean is using big RSA keypairs a large overhead? Would lowering the key size increase the effective bandwidth a little?
The RSA key size only matters at the time when the connection is established. The key size can matter if one of the machines is slow, as larger keys mean longer computations, but its impact on connection times is negligible.
If throughput is a problem, compress the connection:
If connection establishment time is a problem, make sure to activate a single master SSH connection and use slave mode for subsequent connections.
If latency is a problem, there's not much you can do except adapt your habits. If the latency is so high that interactive programs are painful to use, type commands locally and send them over when done (Emacs shell mode is nice for that). Do file management over SSHFS (except remote-to-remote copies).
Avoid needing remote X as it's both latency-sensitive and bandwidth-consuming. If you really must, NX is the best of the crop (but it's painful to set up because it's not free software so distributions don't provide it; this may change as free clones are emerging).
RSA keypairs are only for authentication and for exchange of symmetric keys, which is used for encryption of connection. You can try to use a symmetric cipher, which is not as hard for computation as default cipher is, i.e. blowfish. But this will not do with throughput, but with CPU utilization...