Em um caso muito semelhante, foi um dos scripts update-motd.
O seguinte foi o truque:
sudo rm /etc/update-motd.d/90-updates-available
Aqui está um pequeno ajudante que mede o tempo de cada script:
$ for f in /etc/update-motd.d/*;do echo $f;time $f;done
/etc/update-motd.d/00-header 0m0.007s
/etc/update-motd.d/10-help-text 0m0.005s
/etc/update-motd.d/90-updates-available 0m49.163s
/etc/update-motd.d/91-release-upgrade 0m0.152s
/etc/update-motd.d/98-fsck-at-reboot 0m0.015s
/etc/update-motd.d/98-reboot-required 0m0.003s
(output reduced to the relevant parts)