I had the same issue today on v3.4.3.855.
I set the api key using the required command, then when I ran the push I got this warning:

WARNING: No API Key was provided and no API Key could be found for ‘https://www.nuget.org/api/v2/package‘

and was asked to login using username and password.

So the issue for me was, when I ran: nuget SetApiKey abc...def, I noticed that in the config file ("%Appdata%\Roaming\Nuget\NuGet.Config") it added a key for https://www.nuget.org, when I changed to to the full path it worked fine -> https://www.nuget.org/api/v2/package

So the bug appears to be in the SetApiKey command, not setting the correct key (for the push case anyway)

nuget.exe setApiKey [key] -source https://www.nuget.org/api/v2/package

nuget.exe push won't use API Key