I deal with this by having an additional pair of switches between the Palos and Routers. I use HSRP on the switches for failover. if a circuit fails, the active PA can still find the route to whichever router is active. The Routers and the PAs all sit on the same vlan. The routers themselves are using BGP with our registered AS number and multiple prepends to create a prefered route out our primary ISP. To handle a failure deeper in the ISP, but not at our local link, I use SLAs on the routers to shut down the BGP neighbour, which will force a cutover to my backup. On the routers inside interfaces, I create a subinterface using HSRP so each router uses the same gateway IP, so no matter which router is active, the same gateway IP is responding. This allows you to use Active/Passive in your config.
... View more