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).