Embora eu não sofra do mesmo problema, fiz uma vez e usei o Apt-Fast. Abaixo está o que o autor afirma fazer com instruções de como instalá-lo e usá-lo. Eu não uso isso desde 11.04, mas notei uma considerável diferença de velocidade quando eu fiz isso.
OApt-fast é um utilitário de linha de comando simples que pode tornar a instalação e atualização de software no Ubuntu / Debian muito mais rápida.
O Apt-fast usa o aplicativo Axel, que acelera os downloads de HTTP / FTP usando várias fontes para um arquivo. Autor afirma que, apt-fast poderia fazer suas instalações e upgrades até 26x mais rápido!
Faça o seguinte no Terminal para instalá-lo.
sudo add-apt-repository ppa:tldm217/tahutek.net
A partir de 2 de abril de 2012, apt-fast não possui um repositório preciso. Você tem que editar suas fontes de software como o autor não fez um pacote para Precise. Então você tem que lançá-lo a partir do terminal.
Vá para o separador Outro software e clique em
http://ppa.launchpad.net/tldm217/tahutek.net/ubuntu precise main.
Em seguida, clique em Editar.
Altere o campo que diz "preciso" para "onírico" e clique em OK. Também faça isso na linha que diz (código-fonte).
Feche as fontes de software e coloque essas linhas no terminal:
sudo apt-get update
sudo apt-get install apt-fast
Feche e reabra o terminal novamente e tente usar apt-fast em vez de apt-get . Você deveria ver a diferença.
Esta é uma edição: me deparei com O que é o apt-fast e devo usá-lo? depois que eu respondi o seu que talvez seja útil.