Ich klinke mich hier auch mal ein, weil ich ein gleiches Problem habe, das ich bisher immerhin zur Hälfte lösen konnte.
Grundsätzlich funktioniert das mit dem autoremove so: Alle Kernel und Header-Pakete sollten eigentlich als "auto-installiert" durch apt markiert sein, also nicht als "manually installed". Dadurch werden sie theoretisch von autoremove gelöscht, wenn keine anderen Pakete mehr eine Abhängigkeit zum Kernel oder Header besitzen. Der aktuelle Kernel ist wohl geschützt, weil das "linux-image-generic"-Paket eine Abhängigkeit darauf besitzt, und "linux-image-generic" sollte als manuell installiert markiert sein. Ein oder zwei ältere Kernel werden zusätzlich vor autoremove geschützt, indem eine Datei /etc/apt/apt.conf.d/01autoremove-kernels automatisch erzeugt wird, in der eben diese Pakete aus autoremove ausgenommen werden.
Bei mir war jetzt das Problem, dass die ganzen linux-image-Pakete als "manuell" installiert markiert waren, warum auch immer, und daher nicht durch autoremove entfernt wurden. Möglicherweise wird ein neuer Kernel als manuell installiert markiert, wenn der alte bereits so markiert war. Ich hab jetzt mal alle alten Kernel per
apt-mark showmanual | grep linux-image | xargs sudo apt-mark markauto
als automatisch installiert markiert (danach eventuell linux-image-generic bzw. die gewünschten Metapakete wieder als manuell installiert markieren).
Danach hat autoremove erfolgreich den ganzen alten Krempel entfernt. Und wie üblich zwischendurch ständig die Grub-Konfiguration neu erstellt, was jedes mal eine gefühlte Ewigkeit dauert, aber das ist ein anderes Thema.
Leider habe ich auch noch eine Menge Kernelheader installiert, und da mag das irgendwie nicht klappen.
apt-mark showmanual | grep linux-headers
liefert nichts (habe linux-generic manuell installiert, wodurch wohl keine linux-headers-generic-Manuellinstallation nötig ist, um die aktuellen header zu behalten). Mit "showauto" hingegen gibt es eine ganze lange Liste von Headern aus. Trotzdem will autoremove die Header nicht entfernen. Obwohl es wohl auch keine Reverse Depends gibt, die ich manuell installiert habe:
$ apt-cache rdepends linux-headers-3.13.0-36
linux-headers-3.13.0-36
Reverse Depends:
linux-headers-3.13.0-36-lowlatency
linux-headers-3.13.0-36-generic
Weiß jemand, woran das liegen könnte?