Recently, I experienced an issue with ssh authentication – password prompt taking too long on one of the linux servers. After some research on internet, I found the solution which I would like to share.
1. Turn off - UseDNS by setting the value to "no" in your /etc/ssh/sshd_config
2. Restart sshd Demon
# service sshd restart
Once you restart sshd demon, you should experience the password prompt appearing instantly.