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.