php5-mcrypt
está localizado no repositório universe
.
Abra o Dash, acesse Software and Updates
e verifique o repositório universe
(software gratuito e de código aberto mantido pela comunidade).
OR
Execute o comando abaixo no terminal para ativar o repositório universe,
sudo add-apt-repository universe
Então:
sudo apt-get update
sudo apt-get install php5-mcrypt
Deve funcionar.