In this letter, we measure the rest-frame optical and near-infrared sizes of ten quiescent candidates at 3<z<5, first reported by Carnell et al. (2023a). We use James Webb Space Telescope (JWST) Near-Infrared Camera (NIRCam) F277W and F444W imaging obtained through the public CEERS Early Release Science (ERS) program and imcascade, an astronomical fitting code that utilizes Multi-Gaussian Expansion, to carry out our size measurements. When compared to the extrapolation of rest-optical size-mass relations for quiescent galaxies at lower redshift, eight out of ten candidates in our sample (80%) are on average more compact by ∼40%. Seven out of ten candidates (70%) exhibit rest-frame infrared sizes ∼10% smaller than rest-frame optical sizes, indicative of negative color gradients. Two candidates (20%) have rest-frame infrared sizes ∼1.4× larger than rest-frame optical sizes; one of these candidates exhibits signs of ongoing or residual star formation, suggesting this galaxy may not be fully quenched. The remaining candidate is unresolved in both filters, which may indicate an Active Galactic Nuclei (AGN). Strikingly, we observe three of the most massive galaxies in the sample (log(M_/M_⊙) = 10.74 - 10.95) are extremely compact, with effective radii ∼0.7 kpc. Our results indicate that quiescent galaxies may be more compact than previously anticipated beyond z>3, even after correcting for potential color gradients. This suggests that the size evolution of quiescent galaxies is steeper than previously anticipated and our current understanding is biased by the limited wavelength capabilities of the Hubble Space Telescope (HST) and the presence of negative color gradients in quiescent galaxies.