I would go with priority queuing. RSVP is complicated, and between two routers doesn't make much sense to me. You have control of the interfaces, so you can allocate bandwidth the way you want.
Priority queue always goes first, so you could put traffic in the priority queue and even though you're not doing the rate limiting the heartbeat traffic will still be at the head of the line. If the link is congested it can still be dropped by the SP, so it's not great if you expect congestion. If you configure the "bandwidth" statement correctly on the interface, this should work ok though.
Better option: shape the traffic out of the interface to the speed the service provider guarantees. Then the priority queuing mechanism will provide the configured bandwidth to the heartbeat traffic. We shape our MPLS links because they're provided as sub-interfaces and have no native queuing.
Sample config (for a 1 Mbps service with a 512k priority queue)
policy-map SHAPE
class class-default
shape average 1000000
service-policy PRIORITY
!
policy-map PRIORITY
class HEARTBEAT
priority 512
!
interface gigabit 0/0
bandwidth 1000
service-policy output SHAPE
The nested policy map PRIORITY handles the queuing, and the parent map SHAPE ensures you don't oversubscribe your bandwidth.
Good luck,
Ryan