This is really something the SSH Server developers should consider. The cause of this annoyance is because of failed DNS lookups on your IP address, which is especially common for many dedicated/col-located servers and also computers on internal NAT/private networks.
The chances are this is the cause of your SSH Slow/Delayed Login problems.
Add this line to disable reverse DNS lookups when someone is logging into your SSH Server:
*Don't forget to restart your SSH daemon for the change to take effect!
It would make sense for this option to be disabled by default, especially considering that someone could have a fake or invalid reverse DNS which makes it impossible to find who was really logged in or trying to login.
The SSH daemon should not initially due any reverse DNS or at least allow the login process to continue and try a few more times during the session to find the reverse DNS if it must.
Another symptom aside from it being slow is if you debug the SSH client and see things freeze here:
debug1: SSH2_MSG_SERVICE_ACCEPT received
The problem will be solved once you apply "UseDNS no" to you sshd_confdig and restart SSH.