Tempos de login de 5 a 20 minutos, mesmo para o login inicial, não são normais.
Existem algumas coisas que podem estar causando isso:
-
Você está usando perfis de roaming? Em caso afirmativo, esse usuário possui arquivos muito grandes no perfil? Isto pode ser porque, como eles têm que sincronizar com o novo computador. Mesmo com perfis de roaming, o redirecionamento de pastas ainda deve ser usado para locais onde os usuários armazenam dados, como as pastas da área de trabalho ou de documentos, para evitar isso.
-
Você possui políticas de grupo, chaves de registro de execução única, scripts de login, etc. que são executadas somente na primeira vez que um usuário faz login? Se assim for, estes podem contribuir para o problema.
-
Existe um controlador de domínio que seja "local" para o usuário? Se o controlador de domínio mais próximo estiver do outro lado de um link de rede lento / não confiável, o aplicativo inicial do GPO do usuário e de outros itens de login poderá demorar um tempo incomumente longo.
Como mencionado em um comentário sobre sua pergunta, a Microsoft possui ferramentas para traçar o perfil do desempenho de login lento. Você deve utilizar o Windows Performance Toolkit aqui, pois ele fornecerá uma ótima visão.