Now not everyone is interested in Uber Bosses. They should be considered additional challenges, something you actively look for when you've facerolled Diablo over in Inferno.
With this in mind, it could be a good idea to make the Keywardens a trigger as opposed to an always present enemy. Maybe you find a pedestal with a key on it (or without, maybe just a little box which MAY contain a key), with an orange, legendary glow to it. Once activated, the Keywarden spawns and the fight begins. This way, players would have time to prepare for the fight, or even avoid it completely, if they wish to do so.
I have yet to die to a Keywarden myself, whether in SC or HC, but I'm not at higher difficulty levels, so I've always managed. But I think HC players would agree, especially if Ubers are not one of their goals, that Keywarden sometimes pose a disproportionate and perhaps unnecessary threat.