котаны

Почему может неработать проверка по ssh?

ssh есть, ключи, пароли, все настроено и проверено

даже libssh стоит

Но проверка грит Cannot establish SSH session: Unable to exchange encryption keys

Обгуглено уже всё что гуглилось, но не помогает

Что делать, куда копать?

может попробовать с теми же ключами от имени пользователя сервиса с -vv и посмотреть, как пойдет?

сделано, проходит

м.б. забикс собран без поддержки ssh? Как глянуть с какими флагами его собрали?

Глянул в логи

25816:20171015:192559.337 SSH2 support: YES

Ну как бы вообще всё пучком должно быть