I've been suffering from this on CentOS 7 for quite some time now but haven't really have time to dig into it.
Just today, I noticed the line after a successful logon:
Last login: Fri March 27 16:03:23 2016 from gateway.
Aha, now I know where the time has been spent. The SSHd must have taken a long time to figure out the host name of my login IP.
I've suspected this before, but in my sshd_config file, the line "UseDNS" was commented out, so I thought it must be something else.
A simple "man sshd_config" revealed that, "UseDNS yes" is actually the default setting:
UseDNS Specifies whether sshd(8) 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”.
So I just add "UseDNS no" in the configuration file and restarted sshd. Problem solved.