On a newly installed Linux server, it always takes about 15 seconds to do an SSH login. That's quite a delay.

So we checked the sshd_config file. There is an option

GSSAPIAuthentication yes

Change this option to "no". Then restart sshd. The login delay is instantly gone.

Apparently there is some bug(s) related to this. See Bug: SSH with GSSAPIAuthentication option on SSH servers are very slow

What is GSSAPIAuthentication?

When it is turned on, it allows user authentication using GSSAPI (Generic Security Service Application Programming Interface). GSSAPI is a function interface that provides security services for applications in a mechanism-independent way. This allows different security mechanisms to be used via one standardized API. GSSAPI is often linked with Kerberos, which is the most common mechanism of GSSAPI.