Quasi-PDFs provide a path toward an ab initio calculation of parton distribution functions (PDFs) using lattice QCD. One of the problems faced in calculations of quasi-PDFs is the renormalization of a nonlocal operator. By introducing an auxiliary field, we can replace the nonlocal operator with a pair of local operators in an extended theory. On the lattice, this is closely related to the static quark theory. In this approach, we show how to understand the pattern of mixing that is allowed by chiral symmetry breaking, and obtain a master formula for renormalizing the nonlocal operator that depends on three parameters. We present an approach for nonperturbatively determining these parameters and use perturbation theory to convert to the MS-bar scheme. Renormalization parameters are obtained for two lattice spacings using Wilson twisted mass fermions and for different discretizations of the Wilson line in the nonlocal operator. Using these parameters we show the effect of renormalization on nucleon matrix elements with pion mass approximately 370 MeV, and compare renormalized results for the two lattice spacings. The renormalized matrix elements are consistent among the different Wilson line discretizations and lattice spacings.