É possível que o seu DNS esteja configurado incorretamente, e os sistemas estão tentando fazer uma pesquisa reversa de DNS que expirou.
Tente instalar Wireshark para verificar se os pacotes VNC foram confirmados e se não há problemas de firewall / bloqueio de portas.
(Eu tive o problema acima com SSH antes. Definindo UseDNS=no
corte de 4 a 5 segundos do tempo total de login. E não consegui consertar os registros DNS porque era um roteador doméstico que não suportava isso.)