Your circuit isn't turning the fan fully on and fully off. It will always provide some power to the fan. The transistor will get hot, because there will be current thought it and a voltage across it at the same time. The transistor is rated at 625 mW (
https://www.onsemi.com/pub/Collateral/P2N2222A-D.PDF) so when there is 4 V across it, anything over 150 mA will overheat it. You don't say how big the fan is, or how big the battery is, but 5 V fans that only take 150 mA are quite small and they may take more current when starting up.
What you need is a suitable power supply for the fan, at the correct voltage. That might be a 9 V battery and a regulator. A PP3 battery won't run a 150 mA fan for long. That current is really too much for a PP3, but there are larger batteries.
A linear regulator will get hot, and a switch-mode regulator will be more complicated.
To turn the fan on and off, you need some sort of amplifier, maybe a couple of transistors, that switches fully on and fully off, so that it doesn't run in a partially on mode where it gets hot. You can switch the 9 V going into the regulator, or the 5 V coming out of the regulator. Some regulators have a low-power input that allows then to be turned off and on.
You could just use a power bank which will be fine at up to 1 A. Some will turn off if you don't take current from them, when the fan stops, and need turning on with a button.