That doesn't surprise me, as Rails 5 is still in beta and a lot of gems with Rails dependencies may not have been updated to declare compatibility with Rails 5 pre-releases yet.
Looking at the DEBUG_RESOLVER output, it looks like the main problem comes from transitive dependencies on rack. Rails 5 declares a dependency on the Rack 2.0 pre-release version, however some other gems with rack dependencies restrict it to 1.x versions.
Note that in order to backtrack to 0.6.1 of oauth2, it also had to use an older version of omniauth-oauth2 (1.0.2 instead of 1.4.0), and an earlier version of omniauth-github. This recursive backtracking to earlier versions with looser constraints is what causes resolution to be slow.