PuTTY slow connecting to Linux SSH server [duplicate]
I'd also look at your DNS... maybe. Can the server you're connecting to resolve DNS properly? Could you add a temporary host entry with your source IP in the server to test?
See: SSH takes about 30 seconds to connect on my computer