Alguns usuários ainda preferem o Synaptic e tem reclamado da lentidão na busca, então saiba que é possível deixar a busca muito mais rápida, para isso basta apenas instalar um pacote, e ele vai resolver o seu problema de vez.
Para isso execute os comandos abaixo:
sudo apt-get install apt-xapian-index -y