We present a novel method of machining optical fiber surfaces with a CO${}_2$ laser for use in Fiber-based Fabry-Perot Cavities (FFPCs). Previously FFPCs were prone to large birefringence and limited to relatively short cavity lengths ($le$ 200 $mu$m). These characteristics hinder their use in some applications such as cavity quantum electrodynamics with trapped ions. We optimized the laser machining process to produce large, uniform surface structures. This enables the cavities to achieve high finesse even for long cavity lengths. By rotating the fibers around their axis during the laser machining process the asymmetry resulting from the lasers transverse mode profile is eliminated. Consequently we are able to fabricate fiber mirrors with a high degree of rotational symmetry, leading to remarkably low birefringence. Through measurements of the cavity finesse over a range of cavity lengths and the polarization dependence of the cavity linewidth, we confirmed the quality of the produced fiber mirrors for use in low-birefringence FFPCs.