Are you using iCloud for sync or another account like a Gmail account?
When troubleshooting notes sync I always check “the cloud” to find out where the disconnect is.
Example using iCloud:
Make a new note (or an edit) on Mac, go to iCloud.com to see if it is there. If it is in iCloud, then you can check to see if has synced to iPhone as well.
Another question, does this happen with new notes only, edits to existing notes, or both?