SSH and GIT auth suddenly stopped working

I've been happily pulling from my repository for months, until now.. :'(

For the first time ever git now asks me to add github.com to the known_hosts file. It never did that before, I even didn't have a .ssh directory until after I say 'yes' to the question below.

# git pull

Host 'github.com' is not in the trusted hosts file.
(ssh-rsa fingerprint md5 16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48)
Do you want to continue connecting? (y/n) y

/usr/bin/ssh: Connection to [email protected]:22 exited: No auth methods could be used.
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

I can't figure out what could have changed... doing git status works, but I can't pull anything.

I can't do a ssh -vvv, as this is on a small embedded linux system, and apparently ssh didn't compile with the verbose option, so I can't really know what's going on.

Shouldn't I be able to pull from repo's without having to add a github ssh key? This all happens on a small embedded systems, that I deploy on various places, so I don't like to add any account details, I just want it to pull the latest version from github.

My git config:

[core]
        repositoryformatversion = 0
        filemode = true
        bare = false
        logallrefupdates = true
[remote "origin"]
        url = [email protected]:MyUser/MyRepo.git
        fetch = +refs/heads/*:refs/remotes/origin/*
[branch "master"]
        remote = origin
        merge = refs/heads/master

I've tried changing git to https, but that gives me a certificate error instead. (I've redacted the user and repo name)

As you mention this is on an embedded system, make sure the date & time is correct. I had some issue with HTTPS where the system would basically think it was in 1970 and refuse Github certificate.

Also you can find the expected SSH host keys here: https://help.github.com/articles/github-s-ssh-key-fingerprints/. It is a good idea to check them when something that used to work now goes weird, it might be a man in the middle.