You ever been trying to connect to a server using SSH and it takes years to connect? Maybe not years, but hours.
Yup, I've waited over an hour before just to make an SSH connection to a server.
I've never been able to figure it out until now. The issue was because of my hosts file. My server had been running on two IP's. It still is, and is still capable of utilizing both. However, I needed to give one card specific control to handle most all of the network requests.
In my router, I passed all incoming connections to x.x.0.x. Internally, I wanted it going to x.x.1.x. In my hosts file, I wound up setting the IP to x.x.1.x, but in my DNS, it was pointing to x.x.0.x. That's exactly the problem.
When you set up your own DNS scheme, make sure the hosts file matches it.
Short and sweet, I'll bet that's the answer to most all of these long ssh login times.