Let's do some math! According to the SSH handshake described here[1], I believe there are 6 one-way trips. Given communication times according to this[2], we can average a one way trip to be about 11min.
6 trips x 11 min each:
That is 66min for the handshake.
Full handshake requires a few hours of round trips.