Primeiro, identifique por que é lento. Não é claro da sua descrição onde está o problema.
Etapas que eu gostaria de executar "strace dig google.co.uk" dê uma olhada nas chamadas do sistema e nesse momento entre elas, onde o tempo é gasto?
Se é a rede, o que o ping mostra no seu gateway / roteador? Perda de pacotes e rtt.
verifique as configurações do seu roteador, pode haver um software antivírus / malware inteligente que intercepte o tráfego de DNS.
Você também pode tentar hping3 e testar diferentes tipos de tráfego. Você vê os mesmos atrasos na porta 80 tcp, como faz 53 udp?
Até que você consiga resolvê-lo, talvez, mesmo depois de considerar a execução de um servidor de DNS em cache na sua caixa do Ubuntu, ele pode ajudar a torná-lo aceitável.