После обновления пакета openssh-server из репозитария до последней версии попытка соединиться с обновлённым хостом SSH-клиентом SSH Secure Shell (www.ssh.com) заканчивается неудачей с следующим сообщением об ошибке: Server responded "Algorithm negotitation failed" Key exchange with the remote host failed. This can happen for example if the remote host computer does not supported the selected algorithms. Соединение другими ssh-клиентами (putty, openssh-client) происходит нормально.
*** Bug 8605 has been marked as a duplicate of this bug. ***
В этом ничего удивительного нет, в sshd_config изменилось значение по умолчанию параметра Compression с "yes" на "delayed". Если вам необходимо поддерживать старых или несовместимых клиентов, то придётся вручную вернуть прежнее значение.