Utilizing Internet links in an overlay network to save costs is becoming a widespread solution for enterprise cloud service architectures. However, existing methods struggle to effectively transfer data through cross-region Internet links with high loss rates and latency, which makes it challenging to reduce the 95th percentile bandwidth cost. We propose FeRN, a hybrid node-to-node loss recovery design that focuses on the optimization of Internet links between each pair of nodes, decreasing the end-to-end loss rate of various applications, including bulk data transfer, latency-sensitive and short-lived ones. FeRN employs real-time forward error correction (FEC) coding with dynamic redundancy to address varying loss patterns on Internet links. Experiments with real-world traces demonstrate that compared to TCP Cubic, FeRN can effectively reduce end-to-end loss rate, thus increasing throughput by 200%, reducing 99th percentile tail latency by 32%, and reducing short flow completion time by 17%.