msdb.dbo.sysjobhistory data gets deleted whenever SQL Server services are restarted
My response is based on possible reasons of problem.
Make sure you have configured History setting properly and the job to purge history scheduled properly. To validate these settings:

Right click on SQL Server Agent and got to Properties.



Go to History tab.



Make sure setting is configured properly.



The job named syspolicy_purge_history used to execute above settings.

So right click on the job in Jobs folder in SQL Server Agent and check Schedule of the Job.



It should be scheduled according to your requirement.

Thanks!