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.

The easy solution to SSH Login Problems

Edit /etc/ssh/sshd_config

Add this line to disable reverse DNS lookups when someone is logging into your SSH Server:

UseDNS no

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.