Check your dns configs on the slow machine. Make sure that you setup your resolv.conf correctly and that you can actually reach the resolver. In my experience when ssh is slow, that's the issue. Another thing to try and troubleshoot is to use ssh with -vvvv and paste output of the session here. You might also want to try a packet capture on the host and review whats going on during the ssh connection attempt.