The line from Bicester North heading in the opposite direction as London goes to Birmingham, from where you can get trains to Edinburgh by a variety of routes.
As you may have seen, the route via London is more expensive but faster. If other local stations are possible, Oxford and Banbury also offer connections via Birmingham to the North of England and Scotland.
According to Railplanner, via Birmingham and the West Coast (Virgin) is the fastest route to Edinburgh. The first train leaves Bicester North at 6:47, arr Bham Moor St at 8:02, dep Bham New St at 8:20, arr Edinburgh 12:21 (journey time 5h34m). Most journeys via this route are under 6 hours.
All journeys via London take at least 6 hours. So via London is not the quickest. The walk from Moor St to New St stations is signposted and easily done in 10 minutes.
The other route from Birmingham (Cross Country via Sheffield) typically takes just over six and a half hours, without the need to change at Birmingham (changing points can be Banbury or Leamington Spa depending on time of day).
As the Op wants the earliest arrival in Edinburgh, then via London wins with the 5:33 from Bicester North, comfortably in time for the 7:30 KX-Edinburgh which arrives at 12:12.