@Daz

Yes we do have access to the console. What is the workaround?

After 3 days, and no logical fix works, it's time to say your box is either fubar'd or compromised.

In either case, it's not time for a "workaround", it's time to cut your losses and spin up a fresh VPS.

No chance compromised, if it the same problem as mine.

I would have had to have about 10 different servers hacked, running a variety of different software and distros, and, some on different subnets. Probably more chance of me winning the lottery.

The workaround is simply to use puttygen to generate keys. Have a google around.

Then in your home directory if one does not already exist, create a directory .ssh

The key that goes on the server needs to be pasted into a file authorized_keys in the .ssh directory.

Then reconfigure putty or whatever you are using to use the keys to auth.

Mine goes straight in, no problems.

Its far more secure anyway, you can then go on to switch of password authentication later if you wish.

@Daz

Does it even solve the sftp issue as well?

I use Filezilla and Filezilla can use keys too.

Update:
We just hired a server admin to investigate this. He said that the PROBLEM is with the pam_unix module. The module is responsible for the password authentication, thus, the problem. It also explains why SSH keys still work.

He'll be fixing it for us tomorrow.

@Daz

We have a more irritating problem here The console that we use is browser specific and it does not allow Paste. Cant get the key pasted.

Try this then, this also worked for me for some strange reason.

At your console thing -

killall sshd

/usr/sbin/sshd

Then try ssh in, it took ages but worked, I don't think things are entirely borked here there is a timeout that can vbe altered because of that ^^^^ but I don't know which

@ Daz

How long did it take to login? I have increased the timeout to 10 mins... is that sufficient?

@Daz

Yes Indeed finally the SSH login logged in successfully after quite sometime.
However the sftp doesnt seem to login after quite a long time. Is there anything different required to be done for the sftp.

@Daz

Omg... Finally ftp logged in too... after about 15 mins. You are the man!! I will owe you a great deal all my life. You were the medicine to my headache which was running all these days.

Also if possible can you point out what the possible reasons for the sudden change of behaviour could be? So that it helps the others facing this problem too.

Regards,
Maxim

Update: generated SSH keys and was able to login with the SSH keys!

@cbrands

How did u manage to paste the SSH keys using Lish? The paste doesnt work for me in any browsers: chrome,mozilla,ie,safari,opera.

Now your are ssh'd in paste the keys.

I too want to know what has caused this

We didn't have to paste anything in Lish. The keys were generated on our Linode itself, and we copied them through Lish.