Corrigi este problema adicionando a seguinte linha:
Acquire::Languages "none";
no final de /etc/apt/apt.conf.d/00aptitude (use sudo -H gedit /etc/apt/apt.conf.d/00aptitude em um terminal para editar este arquivo).
Depois de fazer isso, sudo apt-get update está sendo executado mais rapidamente.