Large delays (more than 10 seconds) are typically caused by a problem with name resolution:

• Some versions of glibc (notably glibc 2.1 shipped with Red Hat 6.1) can take a long time to resolve “IPv6 or IPv4” addresses from domain names. This can be worked around with by specifying AddressFamily inet option in ssh_config.
• There may be a DNS lookup problem, either at the client or server. You can use the nslookup command to check this on both client and server by looking up the other end’s name and IP address. In addition, on the server look up the name returned by the client’s IP-name lookup. You can disable most of the server-side lookups by setting UseDNS no in sshd_config.