Nach einem Kernel-Update werden immer alle locale-Einträge neu geschrieben, was mitunter recht lange dauert. Die meisten locale-Einträge werden nicht benötigt. Sie lassen sich so entfernen:

1. Im Verzeichnis /var/lib/locales/supported.d/ steht für jede Sprache eine Datei. In jeder dieser Dateien sind die Einträge für alle Variationen. Entweder kann die Datei ganz gelöscht werden (wenn die Sprache gar nicht benötigt wird) oder editiert werden. Die englische Datei sollte zur Sicherheit verbleiben, es genügt aber der Eintrag en_US.UTF-8.
2. Anschließend mit sudo locale-gen die Einträge neu generieren und fertig.