How to sort Map by Key, but with two conditions in Java?

Предлагаю следующий подход:

    SimpleDateFormat sdf = new SimpleDateFormat("MMM-yyyy"); //устанавливаем формат даты, который Вы предлагаете (Месяц-год)
    Date date = sdf.parse(o1); //переводим в Date формат
    Date date2 = sdf.parse(o2);
    return date1.compareTo(date2); //вернет 1 если `data1 идет после date2 и -1 если наоборот. 

Чтобы отсортировать строки по дате достаточно преобразовать их в какой-нибудь класс, представляющий дату или время. Обычно эти классы уже реализуют интерфейс Comparable и не нужно придумывать сложную логику как сравнить November и December. В данном случае у нас есть только год и месяц, поэтому идеально подойдет YearMonth, чтобы не использовать устаревший Date.

• Перенесите ключи карты в новую коллекцию, реализующую интерфейс List, например ArrayList.
• Отсортируйте список используя сравнение не строк, а объектов YearMonth.
• Если нужно - сделайте новую карту по отсортированным ключам.

З.Ы. для правильного парсинга не забудьте указать нужную Local

    Map<String, String> testMap = new LinkedHashMap<>();
    testMap.put("November-2018", "3");
    testMap.put("September-2018", "5");
    testMap.put("November-2017", "2");
    testMap.put("October-2018", "4");
    // карта до сортировки
    System.out.println(testMap);
    System.out.println();
    // список с ключами
    List<String> list = new ArrayList<>(testMap.keySet());
    // сортировка компаратором
    Collections.sort(list, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofPattern("MMMM-yyyy", Locale.ENGLISH); // формат даты
            YearMonth ym1 = YearMonth.parse(o1, dateTimeFormatter); // парсинг
            YearMonth ym2 = YearMonth.parse(o2, dateTimeFormatter); // парсинг
            return ym1.compareTo(ym2); // сравнение встроенным Comparable
        }
    });
    // отсортированный список
    System.out.println(list);
    Map<String, String> sortedMap = new LinkedHashMap<>();
    for (String key : list){
        sortedMap.put(key, testMap.get(key));
    }
    // отсортированная карта
    System.out.println(sortedMap);