@manton It's been a minute since I've been on macOS, but is Sysprefs > Keyboard > Shortcuts not an option?
Create your own shortcuts - Apple Support Change conflicting shortcuts - Apple Support
@scojjac For some reason that does not work for me. Not sure why! I may be on a weird Safari Technology Preview version, so possibly this will fix itself later.
@manton Not sure if you're a vim person, but I have been using Vimari for most of a year and it's great for keyboard nav of all sorts of stuff in Safari. Even for a handy back button, it might warrant a look.