If you are SSH'ing to a server and having to wait for the user name and/or password prompt the issue could be more than just a slow connection. There are a couple of common things to check if you are having to wait anywhere from 10 seconds to over 1 minute to get your session established.
1. DNS reverse mapping not resolving:
The SSH server may be trying ot perform a reverse lookup on the client trying to connect. If DNS doesn't response quickly, either with the host name or a 'not found' reply, then this attempt will continue until it times out. Modify your /etc/ssh/sshd_config to:
2. SSH may be trying too many authentication types:
SSH may be configured to try PAM, GSSAPI, or some flavor of shared key authentication. You can change the setting:
If you are using PuTTY you may also want to check the settings there. If you are trying to connect using GSSAPI in putty but the server isn't set to use it then you will create a delay while it attempts this. One tell tale sign that GSSAPI is enabled on the client side and is failing is getting an "Access denied" message at the prompt (illustrated below) yet authentication eventually succeeds.
login as: user
Last login: Tue Oct 1 01:23:40 2012 from localhost.com
Uncheck the "Attempt GSSAPI authentication" box and see if this speeds things up.