If I directly connect to Server A, using public key auth from my computer, it takes <0.5 s. But if run the same ssh command from Server B (to connect to Server A) it freezes for about 15 s at the following line : (complete log)

debug2: ssh_connect: needpriv 0

Since I can ssh normally, I assume it is a configuration issue in Server B.

Also, I've tried sshing from B to A, using another account (with password auth). It too hangs at the same line for the same amount. This leads me to believe that it is system ssh config issue, so I'm posting my /etc/ssh/ssh_config as well.

I ran a diff of my ssh_config vs Server B's. The result gave no dissimilarities.

Both Server A and B are running Lucid.