Rather than a capacitor, which will give an exponential decay curve, you might be better to consider a small RC battery pack which is kept charged by the main supply but feeds the arduino when the main supply fails. The circuit would look similar to what you already have but you'd need a 5 volt regulator for the battery pack and a charge resistor from the main supply, say sufficient to feed a constant 10mA to the RC pack, say something like 220ohms or so. With a bit of developement you could build a fast-charge/float charge circuit so's the battery is charged at a higher rate, say 50mA if it's flat, switching to the 5-10mA when fully charged.