I have had this very same problem for the past 6 months. Even back when I had my note 5. I thought buying a new phone will fix it, well it didn't. My brand new note 8 does the same thing.
I have called Verizon countless times and exhausted every trouble shooting there is. I even said I'm done I'm switching to another cellular service.
They promised to me they will get to the bottom of it. They told me to dial
#832 after every call that had bad connections so they can monitor the calls.
Now I don't want to say it's fixed but since the oreo update today I have not had a problem. I'm keeping my figures crossed.