I stumbled across this a few days ago and thought there must be something wrong on my end. I verified my files with Steam, then tried many different sovereigns and maps. I cheated on the larger maps so I could quickly find where the SK was and teleport a unit there, but I played the smaller maps without cheating. In all cases the result was the same: keys are not needed to enter SK's stronghold.
When a unit reached the tile next to the first gate, the message about needing a key was displayed. I clicked on the only choice, then walked through the gate. The gate didn't do anything, and I didn't get any message. I then walked through the second gate and got a message from the SK. I had one or more choices, depending on how many things I had done and how many others I had met before getting to the SK. After clicking on one of the choices, it didn't matter which, I then battled the SK (and promptly died since I had little or no army).
It is real easy to verify if I am right - just find the SK's stronghold and try to walk through the gate.