Собственно проблема заключалась в том, что для доступа на большинство моих серверов я использовал несколько ключей (как rsa, так  и dsa). Однако ключи были сгенерированы на windows и имели passphrase. После попытки зайти с таким ключом куда либо из linux passphrase ключом не принимался (как будто фраза-пароль была введена неправильно). Сразу скажу, что убирание passphrase в windows ни к чему не привели. Пароль все равно запрашивался.

Однако, решение было найдено. Оказывается, pyttygen по умолчанию сохраняет ключи в собственном формате и нужно было всего навсего конвертировать ключ в формат openssh, что и было сделано.

$ puttygen dsa_win.ppk -O private-openssh -o dsa_openssh.ppk

Бинго.