While the Arduino is indeed overkill, you could always just use a much smaller microcontroller. Something like one of the ATtiny chips would likely work well. You could probably fit the code for this on one of the really small ones - an ATtiny45 for sure, but maybe even something as small as a 13A. These are easily obtained in 8-pin DIP (and cheap!). Plus, the code would be pretty similar to what you are already used to with your Arduino.
This would make a very compact solution with minimal parts. Probably the only thing you might need in addition to the chip is a relay or transistor (depending on current needs), and perhaps a resistor or two and a filter cap on the Tiny. You probably would be fine with the internal oscillator on the microcontroller for your accuracy needs - so no need for external crystal and such.
You should even be able to use the Arduino to program the tiny chip (see the Arduino As ISP sample code that comes with the Arduino software or look up various examples on Instructables.com or elsewhere).