PrivateKeyAuthenticationMethod.Authenticate can take up to 25000milliseconds

Hello,

I am facing a weird issue where connection to a server (SSH or SFTP) can sometimes take a very long time though the network condition are quite good. I have drilled down to Authenticate method of PrivateKeyAuthenticationMethod class and put some tracing around the first WaitOnHandle:

                //  Send public key authentication request
                session.SendMessage(message);

System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
session.WaitOnHandle(_authenticationCompleted);
System.Diagnostics.Trace.WriteLine($"PK AUTH doing {keyFile.HostKey.Name} took {sw.ElapsedMilliseconds} milliseconds");

Here are some results:
PK AUTH doing ssh-rsa took 9108 milliseconds
PK AUTH doing ssh-rsa took 315 milliseconds
PK AUTH doing ssh-rsa took 262 milliseconds
PK AUTH doing ssh-rsa took 310 milliseconds
PK AUTH doing ssh-rsa took 271 milliseconds
PK AUTH doing ssh-rsa took 1126 milliseconds
PK AUTH doing ssh-rsa took 258 milliseconds
PK AUTH doing ssh-rsa took 322 milliseconds
PK AUTH doing ssh-rsa took 8649 milliseconds
PK AUTH doing ssh-rsa took 311 milliseconds
PK AUTH doing ssh-rsa took 2674 milliseconds
PK AUTH doing ssh-rsa took 317 milliseconds
PK AUTH doing ssh-rsa took 260 milliseconds
PK AUTH doing ssh-rsa took 280 milliseconds
PK AUTH doing ssh-rsa took 10827 milliseconds
PK AUTH doing ssh-rsa took 276 milliseconds
PK AUTH doing ssh-rsa took 254 milliseconds
PK AUTH doing ssh-rsa took 271 milliseconds

PK AUTH doing ssh-rsa took 265 milliseconds
PK AUTH doing ssh-rsa took 1694 milliseconds
PK AUTH doing ssh-rsa took 3949 milliseconds
PK AUTH doing ssh-rsa took 315 milliseconds
PK AUTH doing ssh-rsa took 267 milliseconds
PK AUTH doing ssh-rsa took 1021 milliseconds
PK AUTH doing ssh-rsa took 261 milliseconds
PK AUTH doing ssh-rsa took 318 milliseconds
PK AUTH doing ssh-rsa took 256 milliseconds
PK AUTH doing ssh-rsa took 310 milliseconds
PK AUTH doing ssh-rsa took 257 milliseconds
PK AUTH doing ssh-rsa took 321 milliseconds
PK AUTH doing ssh-rsa took 255 milliseconds
PK AUTH doing ssh-rsa took 2486 milliseconds
PK AUTH doing ssh-rsa took 251 milliseconds
PK AUTH doing ssh-rsa took 273 milliseconds
PK AUTH doing ssh-rsa took 252 milliseconds
PK AUTH doing ssh-rsa took 20895 milliseconds

This has been executed twice against 12 servers (physically different, but exactly the same from software perspective) in the same network conditions.
I can't figure out what could be the problem and I can't imagine why such authentication usually takes 300 milliseconds but cam raise up to 25000ms !?

Start at PrivateKeyAuthenticationMethod.Authenticate, focusing on the first session.WaitOnHandle call after the public-key authentication request. Reproduce the variable timings across the reported servers and use equivalent tracing to isolate the cause; done means the intermittent delay is explained and a verified fix or clear diagnosis is documented.