We are using active directory syncing for our profiles with the normal process.Users are not being deleted on SharePoint that have been deleted from our AD.I checked the job runs every hour with no issues.Not sure what to look at next.
The users who have been delete from AD but still presented in SharePoint are known as Orphaned users. It is the default behavior of SharePoint Server.
You can manually remove orphaned users from User Information list or directly remove them from the content database.
Here are your references.