The solution is for those with ssh/sftp access to the server.
Hi all, I just helped my colleague with a real simple fix and it worked. TL;DR all the post that mentioned [resolved] for this particular issue. Anyhow; you'll need to ssh into your server. I'm not sure about EC2 (not sure this is relative reference but here it is anyways > http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ec2-key-pairs.html )
ssh -l <username> <host>
//enter your passwords when prompted
// run the ssh-keygen, at your discretion enter preferred password for the key or leave blank.
//you'll be prompted by interactive options such as saving the private and public key file, we left that blank for our purposes.
Go back to WordPress and update your plugins. Enter your username and password as you would when using sftp client. No need to "Upload Private Key:"
See witness the upload and update install successfully.