Could you burn in the private key using fuses?
Specifially, slides 35-40. You burn a feature fuse to unlock manufacturing test features. The device is personalized with a serial number + told to generate private key + record stored in database. Then, the key is locked in by burning a second feature fuse that disables any future writing to those segments.