We propose an acquisition and reconstruction technique for accelerated free-breathing cardiac MRI acquisitions. For the acquisition, a random undersampling pattern, including a fully-sampled center of k-space, is generated prospectively. The k-space lines specified by this undersampling pattern is acquired with respiratory navigating (NAV), where only the central k-space lines are acquired within the pre-specified gating window. For the outer k-space lines, if the NAV signal corresponding to a k-space segment is outside the gating window, the segment is rejected, but not re-acquired. The reconstruction approach jointly estimates the underlying image using a compressed-sensing based approach, and the translational motion parameters for each segment for the outer k-space segments acquired outside the gating window. The feasibility of the approach is demonstrated in healthy adult subjects using whole-heart coronary MRI with a 3-fold accelerated random undesampling pattern. The proposed acquisition and reconstruction technique is compared to parallel imaging with uniform undersampling with 3-fold undersampling. The two techniques exhibit similar image quality with a shorter acquisition time for the proposed approach (4: 25±0: 31 minutes versus 6: 52±0: 19).