If you look how search algorithm work, the execution time will be wildly different depending on how early it will enter the correct path. Same could be said here. You either are able to explore the whole dungeon in the time limit or you might be shit out of luck. Last demo it was very easy to finish all dungeons, but this time (starting with the demo day seed) in 3 runs I only found a single bedroom, so you can see where I'm going with this - the balance might be shaky if it's dependant on an arbitrary time limit.
Assuming I understand anything about the game at all, improving it could be done the systems way or level design way.
Timer might not be an instant game over, but just applying penalties/making the dungeon harder (or the other way around, giving bonuses for fast finish).
Level design way would be removing the single point of failure of not being able to find the objectives. It could show you where the objectives are (like from behind bars), but player still has to be able to find and reach the entrance. You could also take a tighter experience approach of removing most exploration towards focusing on platforming.