BGP recommended setup with failover

Dear Experts,

We need your advise on our current bgp setup is via Cyberoam UTM firewall from two different carriers.

we have

1. Two carrier links
2. two utm firewall followed by
3. redundant L2 switches

carrier links are terminated to firewall wan ports, bgp is published however only one carrier is working with bgp the other one fails for some reason.

we are unable to use direct public bgp ip addresses instead our network team is using natted private ip's. Perhaps our team is not capable of doing this

Kindly suggest a proper and simple bgp setup with low cost budget devices before the firewall through which we can achieve BGP publishing along with failover and also use our firewall security features. i.e., we want to separate BGP publishing and firewall. If you feel we can still do BGP at firewall level it is not an issue however we want to achieve transparency of ip passthrough (no natted ip's) , failover at carrier level if possible with load balancing.

I am also open for paid consultation via live

Thanks

Regards