SSH too long to connect ;(

Its been observed from my experience few of the remote system takes too long to connect. 

I  had this issue on Redhat server 5.0 32-bit on kernel 2.6.18 with OpenSSH version 4.3.

Below steps solved my problem.

1. try to connect your server with an verbose option, if there are any of the GSS failures, need to turn off in /etc/ssh/sshd_config. You could either comment it out or you could switch off the GSS authentication parameter.

By disabling the above it will quickly prompt for the password field.

2. Once after entering the password and you found it is taking more delay for shell it means that your sshd config is trying to search for the DNS entry.

edit your sshd_config and append "UseDNS=No".

Any changes made in the sshd_config, expects for service restart.

Once after restarting the service, it must solve your problem.