In this Letter, we measure the rest-frame optical and near-infrared sizes of 10 quiescent candidates at 3 < z < 5, first reported by Carnall et al. We use James Webb Space Telescope Near-Infrared Camera F277W and F444W imaging obtained through the public CEERS Early Release Science 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, 8 out of 10 candidates in our sample (80%) are on average more compact by ∼40%. A total of 7 out of 10 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 nucleus. 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 findings provide no indication that the size evolution relation flattens out, and may indicate that the size evolution of quiescent galaxies is steeper than previously anticipated beyond z > 3.