Maybe it's trying to resolve the ip address and that's what takes a long time.

There's an option "UseDNS Specifies whether sshd should look up the remote host name and check that the resolved host name for the remote IP address maps back to the very same IP address. The default is ``yes''.

You could try setting it to "no" (in /etc/ssh/sshd_config)