Isto é quase certamente devido a NSS . sudo (ou qualquer outro programa que precise resolver nomes) pode levar muito tempo se precisar procurar nomes de usuários ou nomes de host na rede.
Primeiro, tente entender qual deles está causando problemas. Dê uma olhada em nsswitch.conf ou faça um teste com outros NSS programas, como ping ou chmod . Se você tiver alguma coisa relacionada à rede configurada para usuários (LDAP, NIS, etc.), verifique se esses serviços estão disponíveis. Se o ping do seu próprio host também levar muito tempo, o problema provavelmente está na resolução do nome do host, e você precisará corrigir suas configurações de DNS.
Também é bom tentar verificar /etc/hosts e /etc/passwd , mas não esperaria que falhas com arquivos locais introduzissem um atraso de 30 segundos.