The easiest approach for your situation is to use keepalived which is an implementation of VRRP.
Install it in Debian Linux on each firewall with:
sudo apt-get install keepalived
Then edit the file /etc/keepalived/keepalived.conf
For the master (something like):
vrrp_instance default-gw {
state MASTER
virtual_router_id 1
interface eth1
priority 100
authentication {
auth_type pass
auth_pass pass1234
}
virtual_ipaddress {
x.x.x.x/xx label eth0:pub
y.y.y.y/yy label eth1:lan
}
}
And the slave config will be the same except with
state SLAVE
priority 101
I may have the config slightly wrong (I just butchered what I had which doesn't have the public side set up with a failover address but two separate addresses), but that's the essence of it. What it does is create a couple of virtual IP address.
Where eth0:pub will be the public one and eth1:lan will be the private one.
If one host goes down, the other takes over.
There are a bunch of examples that you'll find under /usr/share/doc/keepalived/samples
It's quite a powerful tool with quite a few features. You can even load-balance servers.
Unfortunately, the website and documentation on the website hasn't kept pace with the product development so you may find some documentation examples don't work right. I've always found answers for it by googling.
If you're using NAT there is also a product to take over the in memory states. You may or may not need it. But that requires a third networking interface.