Thank you for this thread!
Same problem here -- ssh consistently had a 25second delay before connections would succeed.
Like you, I had "UsePam yes" in my sshd config. Flipping it to "no" & restarting sshd resolved the problem.
The system's uptime is 2 months, so it's possible that rebooting ...