Why does ssh's “password” prompt take so long to appear?

There are several things that can go wrong. Add -vvv to make ssh print a detailed trace of what it's doing, and see where it's pausing.

The problem could be on the client or on the server.

A common problem on the server is if you're connecting from a client for which reverse DNS lookups time out. (A “reverse DNS lookup” means getting back from the client machine's IP address to a host name. It isn't really useful for security, only slightly helpful to diagnose breakin attempts from log entries, but the default configuration does it anyway.) To turn off reverse DNS lookups, add UseDNS no to /etc/ssh/sshd_config (you need to be root on the server; remember to restart the SSH service afterwards).

Another thing that can go wrong is GSSAPI authentication timing out. If you don't know what that is, you're probably not relying on it; you can turn it off by adding the line GSSAPIAuthentication no to /etc/ssh/ssh_config or ~/.ssh/config (that's on the client side).

Let time the login process and see how long it will take:

[root@gislab00207 ~]# time ssh root@ISSLABNTL01
root@isslabntl01's password:
Last login: Fri Oct  4 07:55:03 2013 from 3.60.40.232

[root@ISSLABNTL01 ~]# exit
logout
Connection to ISSLABNTL01 closed.

real    0m45.192s
user    0m0.003s
sys     0m0.005s

You have new mail in /var/spool/mail/root
[root@gislab00207 ~]#

See above it took about 45 seconds to login -------- VERY SLOW

Once You login as root edit sshd_config file and change the UseDNS entry as below. Here I am using sed instead of editing the file.

[root@ISSLABNTL01 ~]# grep -i dns /etc/ssh/sshd_config
#UseDNS yes

[root@ISSLABNTL01 ~]# sed -i 's/#UseDNS yes/UseDNS no/g' /etc/ssh/sshd_config
[root@ISSLABNTL01 ~]# grep -i dns /etc/ssh/sshd_config
UseDNS no

[root@ISSLABNTL01 ~]# service sshd restart
Stopping sshd:                                             [  OK  ]
Starting sshd:                                             [  OK  ]
[root@ISSLABNTL01 ~]# exit

Let us time the login process and see now how long it will takes.

[root@gislab00207 ~]# time ssh root@ISSLABNTL01
root@isslabntl01's password:
Last login: Fri Oct  4 07:55:03 2013 from 3.60.40.232

[root@ISSLABNTL01 ~]# exit
logout

Connection to ISSLABNTL01 closed.

real    0m6.192s
user    0m0.003s
sys     0m0.005s

You have new mail in /var/spool/mail/root
[root@gislab00207 ~]#

See it took now 6 seconds, the time for me to type the password.

It is something that comes wrong from Ubuntu's installation.

To fix it you have to change this line in /etc/nsswitch.conf:

hosts:          files mdns4_minimal [NOTFOUND=return] dns mdns4

And change it for this one:

hosts:          files dns