In this paper we derive a differential identity for linearized gravity on the Kerr spacetime and more generally on vacuum spacetimes of Petrov type D. We show that a linear combination of second derivatives of the linearized Weyl tensor can be formed into a complex symmetric 2-tensor Mab which solves the linearized Einstein equations. The identity makes this manifest by relating Mab to two terms solving the linearized Einstein equations by construction. The self-dual Weyl curvature of Mab gives a covariant version of the Teukolsky-Starobinsky identities for linearized gravity which, in addition to the two classical identities for linearized Weyl scalars with extreme spin weights, includes three additional equations. In particular, they are not consequences of the classical Teukolsky-Starobinsky identities, but are additional integrability conditions for linearized gravity. The result has direct application in the construction of symmetry operators and also yields a set of nontrivial gauge invariants for linearized gravity.