Id replace the EGR valve.
Id also do a throttle body cleaning with a throttle reset.
I assume you have a new/clean air filter, installed correctly, box lid sealed. Intake hose is leak/crack free.
I agree, premium gas does little. I’d look for 87 octane with fuel additives (top tier).