Alternativa para "ocultar" as consultas DNS

Hoje em dia existe uma alternativa pra isso, uma forma de você navegar sem manter em cache os domínios no seu sistema operacional e sem que seu provedor tenha acesso também.

DoH e DoT

Além das alternativas citadas em outras respostas, como VPNs e proxies, existe o DNS over HTTPS (DoH) e DNS over TLS (DoT). Ao usar algum desses protocolos, você usa um servidor terceiro para buscar o domínio mas de forma criptografada. Nesse caso, você estará se expondo apenas ao serviço que desejar usar.

No meu caso eu uso o CloudFlare através do meu navegador, Firefox, ativando a opção de DoH. Assim nem a Microsoft e nem meu provedor tem acesso ao meu histórico.

Potenciais Problemas

• Alguns indivíduos e organizações confiam em DNS para bloquear malware, ativar controles dos pais, ou filtrar o acesso de seu navegador a sites. Quando ativado, o DoH ignora seu resolvedor DNS local e anula essas políticas especiais.
• Quando o DoH está ativado, as consultas de DoH são direcionadas para servidores de DNS operados por terceiros, que podem ver consultas de usuários. No caso do Firefox, a Mozilla implementou uma forte política de Trusted Recursive Resolver (TRR) que proíbe que seus parceiros coletem informações de identificação pessoal. Para atenuar este risco, os parceiros Mozilla são obrigados contratualmente a aderir a esta política.
• O DoH pode ser mais lento que consultas DNS tradicionais por uma margem baixa e, em algumas pesquisas, também foi demonstrado que pode ser mais rápido que consultas tradicionais. Cabe fazer uma pesquisa mais a fundo sobre isso. Eu, pessoalmente, não senti diferença quando troquei.

Fonte: https://support.mozilla.org/pt-BR/kb/dns-sobre-https-no-firefox