How have you configured the CPU_FAN header in BIOS Setup. One option on many mobos is a so-called "Quiet" profile to keep fan noise down. BUT what that really means is that the fan is fixed to run at a slow speed and much reduced cooling. In some situations that may result in the fan stalling and failing to re-start until something boosts its power setting. So, IF you have your CPU_FAN header set this way, change it back to normal automatic control.
On the other hand, if this is an older fan, it is quite possible that its bearings are wearing out and it needs replacement, as others have said.