Recently we have installed a new RHEL5.4 machine. Its located just few kilometers from our office. But when I have observed at the time of logging, the shell prompt is taking considerable time to appear(though connection is taking a fraction of second, after entering the password it’s taking more time). So we did some tweeking and found out this is related to DNS. We have to change dns related entries in ssh_config file to reduce this delay.
Note : Be careful when doing this on production servers. This activity may disconnect all the users from the system who are logged in to that machine using SSH

By default UseDNS option in this file is disable. We have to uncommet this option and then edit this entry to no. As below.. 
Just search for UseDNS..

[[email protected] ~]#vi /etc/ssh/sshd_config 

before config
#UseDNS yes

After config 
UseDNS no 

save and exit the file and then just reload ssh service to take effect what ever changes we did.. 

#service sshd reload.

Now when we try to login, we faced same issue once again. We are puzzled what could be done. We did a debugging with ssh -v option to that server as shown blow.

Related concept:   Configuration of SQUID Reverse Proxy

ssh -v [email protected]
OpenSSH_6.0p1 Debian-3ubuntu1, OpenSSL 1.0.1c 10 May 2012
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to 192.168.100.129 [192.168.100.129] port 22.
debug1: Connection established.
debug1: identity file /home/surendra/.ssh/id_rsa type -1
debug1: identity file /home/surendra/.ssh/id_rsa-cert type -1
debug1: identity file /home/surendra/.ssh/id_dsa type -1
debug1: identity file /home/surendra/.ssh/id_dsa-cert type -1
debug1: identity file /home/surendra/.ssh/id_ecdsa type -1
debug1: identity file /home/surendra/.ssh/id_ecdsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH_5*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.0p1 Debian-3ubuntu1
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Server host key: RSA 89:7f:23:c9:fa:bd:56:5d:97:13:dd:3f:33:3e:13:53
debug1: Host ‘192.168.100.129’ is known and matches the RSA host key.
debug1: Found key in /home/surendra/.ssh/known_hosts:1
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Next authentication method: gssapi-keyex
debug1: No valid Key exchange context
debug1: Next authentication method: gssapi-with-mic
debug1: Unspecified GSS failure.  Minor code may provide more information
Cannot determine realm for numeric host address

debug1: Unspecified GSS failure.  Minor code may provide more information
Cannot determine realm for numeric host address

debug1: Unspecified GSS failure.  Minor code may provide more information

debug1: Unspecified GSS failure.  Minor code may provide more information
Cannot determine realm for numeric host address

debug1: Next authentication method: publickey
debug1: Trying private key: /home/surendra/.ssh/id_rsa
debug1: Trying private key: /home/surendra/.ssh/id_dsa
debug1: Trying private key: /home/surendra/.ssh/id_ecdsa
debug1: Next authentication method: password
[email protected]’s password:

Related concept:   Coroner's Toolkit - For recovering deleted data in Linux/Nix systems

We seen considerable delay in the connection at the above indicated point with red. This is due to the client side issue if you are using Linux box to connect. We have to change the /etc/ssh/ssh_config settings

Change the value of GSSAPIAuthentication from yes to no.

Save the file and exit.

Now try to connect it and see the difference.