Phonons are fundamentally important for many materials properties, including thermal and electronic transport, superconductivity, and structural stability. Here, we describe a method to compute phonons in correlated materials using state-of-the-art DFT+DMFT calculations. Our approach combines a robust DFT+DMFT implementation to calculate forces with the direct method for lattice dynamics using nondiagonal supercells. The use of nondiagonal instead of diagonal supercells drastically reduces the computational expense associated with the DFT+DMFT calculations. We benchmark the method for typical correlated materials (Fe, NiO, MnO, SrVO$3$), testing for $q$-point grid convergence and different computational parameters of the DFT+DMFT calculations. The efficiency of the nondiagonal supercell method allows us to access $q$-point grids of up to $6\times 6\times 6$. In addition, we discover that for the small displacements that atoms are subject to in the lattice dynamics calculation, fixing the self-energy to that of the equilibrium configuration is in many cases an excellent approximation that further reduces the cost of the DFT+DMFT calculations. This fixed self-energy approximation is expected to hold for materials that are not close to a phase transition. Overall, our work provides an efficient and general method for the calculation of phonons using DFT+DMFT, opening many possibilities for the study of lattice dynamics and associated phenomena in correlated materials.