Редактирование ssh_config и включение PasswordAuthentication всегда работало для меня в моих экземплярах. Если вашему приложению не нужно проходить аутентификацию от имени пользователя root, обязательно создайте для него нового пользователя. Также убедитесь, что вы правильно установили пароль для экземпляра. Большинство общедоступных экземпляров зашифровывают пароль root в начальный момент запуска (если они плохо настроены, возможно, при каждой загрузке), поэтому вам обязательно нужно будет установить его, прежде чем использовать.
Если это не сработает, обязательно посетите EC2 форумы для получения более специализированной помощи.