OP, the point of the posts above is you appear to assume that you must replace BOTH the FAN part of your CPU cooler AND the heatsink part that is fastened to the top of the CPU chip by screws, etc. To do that you'd need to remove that entire assembly, clean off the CPU top, and install a whole new cooler with fresh thermal paste.
It is easier to remove ONLY the fan - that is, detach it from the heatsink part without ever removing the heatsink from the CPU. While the heatsink is exposed completely, you should use a thin probe or something to ensure that all dust and junk accumulated between the fins is loosened and blown out so that full airflow is ensured. Then you mount a new fan in its place. using the same fastening system. Most CPU cooler systems use "standard" fans of a common size, so you need to look for a replacement with a few charateristics.
To help with this, tell us what that old "stock CPU cooler" unit is - maker and model if possible. The things you need to look for are:
SIZE - a fan size is the dimension in mm of one SIDE of the square frame, like 80, or 90, or 92, or 120, etc.
ELECTRICAL - older fans have THREE wires that end in a connector about 3/8" wide with THREE holes, and two ridges down one side. Newer ones have FOUR wires and holes, and are slightly wider to allow for that 4th hole. Buying the same type makes the swap simple. Buying the other type means you would need to make a small adjusment in a setting of the CPU_FAN header in BIOS Setup.
AIR Flow - this is the max airflow spec for a fan. Higher is better, but you do not need vastly more than you have.
PRESSURE - this is a spec for the maimum backpressure (airflow resistance) the fan can overcome and still blow air. For a heatsink with narow spaces between fins the fan needs a higher rating here than a case ventilation fan. Typical values are over 2 mm of water.
NOISE - expressed in dB, this is the max noise it makes at full speed. Less is better for your ears, but this spec is less important than others.
If you tell us what old one you have, we can advise what ones you could buy and how to replace.