No, in general capacitors will have the same capacitance no matter the voltage, you don't get less capacitance at lower voltage. Ceramic capacitors have an important exception... their capacitance can DECREASE as the voltage gets close to their maximum rating, see
https://pdfserv.maximintegrated.com/en/an/TUT5527.pdf (Temperature and Voltage Variation of Ceramic Capacitors, or Why Your 4.7μF Capacitor Becomes a 0.33μF Capacitor)
You could use a switching regulator instead of a LDO to increase the time... you'll find such regulators that can be up to 96-98% efficient, compared to LDOs which will always be as efficient the smallest the difference between input and output voltage is.
With 12v in , 5v out, you get at best 41% efficiency, get something like an AP65111 from Diodes Inc. and you get up to around 95% efficiency:
https://www.diodes.com/assets/Datasheets/AP65111A.pdfSee page 5, second chart from the left, you get ~ 90% efficiency at 0.1A output and up to ~95%. So at least twice as efficient as your LDO, reducing the need for big capacitance even further. I only suggest this particular regulator because it's cheap (<0.4$ on
digikey if you buy 10 or more and it's relatively easy to solder, easy package to deal with, and can work with tiny smd inductor and resistors so very little footprint)
You could add a tiny shottky diode in front and from there use a zener or resistor divider to detect when the voltage drops
12v ----> tap for detect input voltage ---> diode ---> bulk store capacitor --> switching regulator -> your circuit.
diode will prevent you from measuring the voltage on the bulk capacitor.. at very low currents like 0.1..0.5A you can find diodes that only drop only ~ 0.2v so you don't lose much. Use either a zener diode or a voltage divider to drop down input voltage to something reasonable like 3v or whatever. you can then use a digital input pin to know when input voltage is removed (though filter that a bit, in case you use for example a round barrel dc jack and power gets interrupted for something like 1 ms by twisting the jack in the socket or something like that)