90% sure it's your PTC heater. I just replaced mine a month ago after the same behavior as yours. Works great now, and the heat is nearly instantaneous. Here's the link to my DIY (with much help/input from the rest of this forum!). Not a terribly hard job, but make sure you don't shock yourself by not following power down procedures/etc. Good luck!
https://www.mynissanleaf.com/viewtopic. ... 7&start=10