How to step down 12v to 5v efficiently
Yes, a switching regulator, buck converter specifically in this case, would be efficient in providing 5 V to the arduino from your 12 V input.

Be careful in how you feed this 5 V to the arduino.  First, check its schematic to see if it is using a linear or switching regulator.  If the latter, they you can feed it 12 V directly without a lot of loss.  If it has a linear regulator, then you may have to remove it so that you can drive its output with nothing on its input.

However, if you're so keen to minimize power consumption, then use a transistor instead of a relay to control the fan, and use your own microcontroller circuit instead of something off the shelf and with extra things you don't need, like the arduino.