An efficient concerted rotation algorithm for use in Monte Carlo statistical mechanics simulations of nucleic acids is reported. The corresponding algorithm "concerted rotations with flexible bond angles" (CRA) for sampling polypeptides was found to be superior to local moves that included only flexible dihedral angles by allowing exploration of a larger conformational space as well as facilitating backbone transitions. The performance of the present CRA algorithm for polynucleotides is compared to two alternatives, a simple update of main-chain torsion angles and a previously reported, concerted rotation algorithm with-fixed bond angles and a mix of flexible and rigid main-chain dihedral angles. The test system is a 12 base-pair duplex B-form DNA helix, and the performance comparisons are made for the system both in a vacuum and with continuum GB/SA solvation. The results demonstrate the superior efficiency of the CRA method over the alternatives.