Going round in circles.
If op is going for a new and better cooler, there's no need to clean the old one. If op is getting a new cooler, it comes with paste either in a tube or pre-applied, so no need to re-paste, just use the cooler paste as is after cleaning the cpu. Directions will be included too, usually.
Paste doesn't transfer heat. It's the silicates and diamond dust and other stuff in the paste that transfers the heat, so even if the paste dries out rock hard, it still works. As long as the seal isn't disturbed. It's like caulking, once the seal is good, it's always good, but break that seal and it's bunk. It doesn't take much with dry paste to break the seal though, one decent hard knock to the heatsink, constant vibrations from a junky fan etc.
Pretty much any cpu cooler for Intel will fit that socket. Intel hasn't changed its pin dimensions in years, so any heatsink designed for any LGA115X will work. The only requirement is how much space you have from the motherboard to the case side.
Cryorig H7 will do a great job on that cpu and at 145mm tall will fit almost any case except those uber slim models.
Idle temps are high, even for the stock cooler, how many case fans you got in that Rosewill? Should be 1 exhaust, 1intake and the psu as exhaust. You might can cheat the fan curve in bios, default is 70 for max, turn it to 60 max at the front fan. That'll spin the front fan faster at lower temps on the curve, supply more intake.