Проверка подлинности с открытым ключом SSH прервалась на всех моих серверах Ubuntu

Хорошо, это сложно.

В последние несколько месяцев все мои серверы Ubuntu 16.04 перестали принимать SSH-аутентификацию с открытым ключом и будут принимать только пароли. Вот некоторые из вещей, которые я пробовал:

1. Аудит всех прав доступа к файлам, связанных с ssh
2. Повторное копирование пабов на серверы с помощью ssh-copy
3. Остановка sshd, apt-purge all SSH и связанные пакеты, затем перезагрузка и переустановка, которая сбрасывает sshd_config, а также сервер ключей
4. Генерация новых ключей на клиенте с большими битами (4096)
5. И почти все остальное Я мог бы найти на эту тему.

Пара интересных моментов:

1. Для всех серверов Ubuntu были запланированы автоматические обновления для применения обновлений безопасности. Они все перестали работать примерно в одно и то же время. Никаких других изменений программного обеспечения не было сделано
2. Все серверы виртуализированы на нескольких платформах. Некоторые в гостях VMware, некоторые в непривилегированных контейнерах LXC KVM, некоторые в качестве гостей KVM.
3. Совершенно новые установки работают нормально.
4. На серверах Debian такой ошибки не было.
5. Журналы отладки не дают никаких сбоев разрешений, сбоев kex или любой другой подсказки, кроме ssh-connection method none [preauth] на нерабочих серверах против ssh-connection method publickey [preauth] на рабочих серверах. (заполните журналы клиента и сервера ниже)
6. Клиентский компьютер, ключи и программное обеспечение одинаковы
7. Если я запускаю sshd через командную строку, я могу нормально соединиться с открытым ключом.
8. Обновление с 16.04 до 18.04 с помощью do-release-upgrade не решает проблему, оно сохраняется.

Журналы сбоев клиента и сервера Ubuntu: https://pastebin.com/Tg3pu8Nw

Клиент и сервер Debian успешно работают (один и тот же клиентский компьютер и ключи): https://pastebin.com/aG5ddrQ5

Любая помощь будет принята с благодарностью.