A tenere traccia dei link visitati è il browser, non il sito web. Il sito può solo tramite CSS scegliere il colore o qualche decorazione usando la pseudoclasse
Se non vuoi questa feature devi avviare il browser sempre in incognito, comunque non è un problema per la privacy come può sembrare.
:visited
, tuttavia non ha modo di sapere di che colore lo vedi veramente: secondo MDN il browser mentirà al sito se prova a sapere di che colore è un link, indicandolo sempre come NON visitato a prescindere da quello che vedi tu.Se non vuoi questa feature devi avviare il browser sempre in incognito, comunque non è un problema per la privacy come può sembrare.