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.