Perturbations of Kerr spacetime are typically studied with the Teukolsky formalism, in which a pair of invariant components of the perturbed Weyl tensor are expressed in terms of separable modes that satisfy ordinary differential equations. However, for certain applications it is desirable to construct the full metric perturbation in the Lorenz gauge, in which the linearized Einstein field equations take a manifestly hyperbolic form. Here we obtain a set of Lorenz-gauge solutions to the vacuum field equations in terms of homogeneous solutions to the spin-2, spin-1 and spin-0 Teukolsky equations; and completion pieces that represent perturbations to the mass and angular momentum of the spacetime. The solutions are valid in vacuum Petrov type-D spacetimes that admit a conformal Killing-Yano tensor.