It seems that quite a few people are having trouble with this…

In the end, the problem appears to be that the client performs a reverse DNS lookup.

Since there was no other choice, I entered the SSH destination’s IP address and hostname in /etc/hosts.
It began connecting instantly.

Incidentally, it had connected from Windows without any problem…

Reference article: http://macnewbie.wordpress.com/2006/08/30/slow-ssh-connections-on-mac-os-x/

In short, the SSH server’s reverse lookup was failing—that was the story.
Afterward, I configured DNS properly and it was OK.