The SSH daemon appears to execute a reverse lookup on inbound IPs to map them to a DNS address. My symptoms were authentication attempts that took a long time to return a password prompt, but thereafter performed as normal.
It seems like the key is to get the server to "know" the host attempting to authenticate, and so tweaking with /etc/hosts is pretty much a quick way to fix the issue.
... takes forever to get password challenge
Within the /etc/hosts on server, add:
That seems to have fixed things. The password challenges flash up immediately. Of course, it might be prudent to set up an internal DNS so each machine doesn't have to have a cobbled host file.