Languages detection order are not preserved (Language doesn't switch)

The order of language detection methods returned by \Drupal\language\LanguageNegotiator::getNegotiationMethods is not preserved which results to unpredictable behavior of a website. For example, on our website we have Url detection method enabled, but languages switching links are actually provided by LanguageNegotiationSession.php (!) which makes our site's language not switchable at all.

This is the original function:

  public function getNegotiationMethods($type = NULL) {
    $definitions = $this->negotiatorManager->getDefinitions();
    if (isset($type)) {
      $enabled_methods = $this->getEnabledNegotiators($type);
      $definitions = array_intersect_key($definitions, $enabled_methods);
    }
    return $definitions;
  }

As you see the definitions are not sorted directly and the resulting order inherits from the order of the $definitions array which is random. For example, I've compared the order of plugins -- how they're read by plugins discovery facility (\Drupal\Component\Annotation\Plugin\Discovery\AnnotatedClassDiscovery::getDefinitions) -- on two different AWS servers and here are the results:

// order on server 1: 
LanguageNegotiationSelected.php
LanguageNegotiationSession.php
LanguageNegotiationBrowser.php
LanguageNegotiationUI.php
LanguageNegotiationUrl.php
LanguageNegotiationContentEntity.php
LanguageNegotiationUrlFallback.php
---
LanguageNegotiationUser.php
LanguageNegotiationUserAdmin.php

// order on server 2
LanguageNegotiationUrl.php
LanguageNegotiationSession.php
LanguageNegotiationUI.php
LanguageNegotiationBrowser.php
LanguageNegotiationUrlFallback.php
LanguageNegotiationContentEntity.php
LanguageNegotiationSelected.php
---
LanguageNegotiationUser.php
LanguageNegotiationUserAdmin.php

As you see they are different. And no matter which order I provide on en/admin/config/regional/language/detection page it's not used at all.