Slow SSH logins could be caused by DNS lookup on the server side. If it takes (too) long time to be prompted for a password the option UseDNS could by a solution (as suggested in the OpenSSH FAQ). On Ubuntu edit the file /etc/ssh/sshd_config and add the following line:

UseDNS no

Restart the SSH daemon

# /etc/init.d/sshd restart

and try to log in again.