I think your puzzle design is great there and I don't think there's a need to randomize levels after failing. Randomized levels might take away from the player experience in this case, unless done carefully. Maybe something like punishing with resources, or score deductions (like if you finished lvl in one go - 3x multiplier, in more than 1 - 2x, more than 3 - 1x, more than 5 - 0.5x, more than 10 -let player to explore next but don't give score) then rats become valuable resources because you want to solve with least runs.
Regarding the tp - I think you can make some "radar thingy" that would notify player - there's a tp nearby, even if it is a simple "!" sign above the player when in close proximity.