Primeiramente vamos atualizar os repositórios:

apt-get update

Depois vamos instalar o software de proxy e o gerador de senhas correspondente:

apt-get install squid apache2-utils

Quando terminar, vamos criar um arquivo de configuração vazio:

rm -rf /etc/squid/squid.conf
touch /etc/squid/squid.conf
chown proxy /etc/squid/squid.conf

Em seguida, vamos criar o arquivo de senhas:

touch /etc/squid/squid_passwd

E garantir as permissões para o proxy:

chown proxy /etc/squid/squid_passwd

Vamos começar a editar o arquivo de configuração:

nano /etc/squid/squid.conf

e adicionar as linhas abaixo (em http_port especifique a porta na qual deseja se conectar ao proxy):

auth_param basic program /usr/lib/squid/basic_ncsa_auth /etc/squid/squid_passwd
auth_param basic realm proxy
acl authenticated proxy_auth REQUIRED
http_access allow authenticated

http_port 1337

forwarded_for off
request_header_access Allow allow all
request_header_access Authorization allow all
request_header_access WWW-Authenticate allow all
request_header_access Proxy-Authorization allow all
request_header_access Proxy-Authenticate allow all
request_header_access Cache-Control allow all
request_header_access Content-Encoding allow all
request_header_access Content-Length allow all
request_header_access Content-Type allow all
request_header_access Date allow all
request_header_access Expires allow all
request_header_access Host allow all
request_header_access If-Modified-Since allow all
request_header_access Last-Modified allow all
request_header_access Location allow all
request_header_access Pragma allow all
request_header_access Accept allow all
request_header_access Accept-Charset allow all
request_header_access Accept-Encoding allow all
request_header_access Accept-Language allow all
request_header_access Content-Language allow all
request_header_access Mime-Version allow all
request_header_access Retry-After allow all
request_header_access Title allow all
request_header_access Connection allow all
request_header_access Proxy-Connection allow all
request_header_access User-Agent allow all
request_header_access Cookie allow all
request_header_access All deny all

Quando terminar, é necessário adicionar o nome de usuário e senha:

htpasswd /etc/squid/squid_passwd nomedeusuário

Posteriormente, pode-se adicionar novos usuários com o mesmo comando. Depois é só reiniciar o serviço e pronto:

service squid restart

Você pode se conectar ao proxy na porta 1337, ou na porta que você configurou, usando o par de nome de usuário e senha especificado.