SSH slow to connect

Whenever I start git push, it takes up to twenty seconds for the passphrase prompt to show up. Every SSH connection with bitbucket.org seems to hang for a very long time after

debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY

and eventually continues without problems.

My ping with bitbucket.org is about 125 ms, which seems normal for the distance (traceroute reports 30 ms between my house to my ISP, the Atlantic Ocean incurs an 80-90 ms increase, and everything else is just details). I doubt that bandwidth is an issue for this specific scenario, because the delay only happens as the SSH connection is negotiated, and the actuall pull/push traffic is fast.