First of all, that is not a definition of heat. Heat is energy transfer due solely to temperature difference. What is described in your post is more like a definition of internal energy (kinetic and potential energy at the microscopic level).
The reason you feel colder with the fan on is the movement of air over your skin increases the rate heat transfer from your skin by increasing the convection heat transfer coefficient. The relevant equation is Newton's law of cooling
$$\dot Q=hA(T_{s}-T_{∞})$$
Where $\dot Q$ is the heat transfer rate, $T_s$ is the skin temperature, $T_∞$ is the bulk air temperature of the air away from the skin, $A$ is the cross sectional area of the skin, and $h$ is the convective heat transfer coefficient. The faster the air moves the greater $h$ is, all other things being equal. In effect, the air movement forces the air close to the skin to carry heat away increasing the efficiency of heat transfer to from the skin to the air.
You've probably heard of the "wind chill factor". For a same air temperature the wind increases heat loss from the skin making the air feel colder than when there is no wind.
Thank you for the answer, that definitely helps, just one question, do
we ignore the motion of air molecules due to fan movement because it's
too small, negligible and fan is not rotating fast enough? or the fan
moving the air in a cold room never creates any heat even in
microscopic levels, no matter the speed of the fan?
Keep in mind the fan does not "create heat". Heat is energy transfer due to temperature difference. I think what you are really asking is if the fan can increase the temperature of the air molecules because the fan increases the velocities of the air molecules. It is possible that the fan could slightly, but not measurably, increase the temperature of the air by "stirring up" the air molecules, since the temperature of the air is a measure of the average translational kinetic energy of the air molecules. But the fan motor coil, which gets hot when the motor is running, would probably have a greater effect on the air temperature.
Hope this helps.