I had the problem that for a particular website that I would occasionally log in to the username field started autofilling with a huge bunch of gibberish. However, no matter how many times I looked in the Safari saved passwords on my Mac that bit of gibberish was no where to be found, but would also autofill. It would even autofill on my iPhone, but it wasn't in the Safari saved passwords.
So the other answer helped me figure it out. That gibberish was saved in the Keychain and not in Safari. Deleting it there fixed my problem. However, if that gibberish was saved in my keychain but was also on my iPhone then that means the keychain was being synced as well, and not just what Safari has saved. So be aware of that as well if you want to remove everything from the cloud. I also know that the keychain shares across the cloud because as soon as I've put a wifi password in on one device then my other devices will connect to that wifi automatically as well. There are several things that get shared and not just your Safari passwords.
UPDATE (restored after being deleted): I'm sorry I couldn't just make this a comment on the other correct answer but at the time of writing I didn't have enough reputation to leave comments so I was forced to write this as an answer against my will. I hope I'm forgiven. (And please don't censor me. I'm all for editing what I wrote for clarity, but what I said in this update is the truth and so help me I might just give up on SE if someone removes it again without asking me about it first.)