The ciphers used have a large impact on the performance.
From faster ones to slower ones:
arcfour >> blowfish >> aes >> 3des
arcfour and blowfish have security problem.
It is also a good idea to enable compression by default so that ssh performs better over a low-bandwidth link, such as a slow Internet connection.