Can an Arduino use a 12 V relay?
This board is designed to work with 5V logic level control, according to the link you provided. I couldn't find a spec sheet so the following is speculative: you supply +12V and ground to the VCC and GND pins, and use a logic level signal on the IN pin to switch the relay on and off via Q1 and the optoisolator.

So, if the logic level signal can control Q1, your relay may actually work as-is. Changing the relay itself may not help if Q1 can't deal with 3.3V gate drive. (Q1 is marked 'J3Y', so it may be an NPN transistor known as 'S8050'. A logic-level MOSFET like a 2N7002 may work better in this application. Again, pure speculation without a spec sheet.)

There's nothing inherently wrong with your relay as far as controlling a fan goes. Overkill, sure, but it will do the job just fine and will scale up to allow you to play with bigger stuff as your confidence grows.