WordPress 6.8.x has new hashing that can be brittle with multisite and object caching. Logging into main site may upgrade the existing password but then hashing could become invalid on other sites. You should investigate your object caching issues. This is just to help you debug to detect a rehashing issue.

wp-68-auto-rehash-password.php

<?php
/*
Plugin Name: Auto rehash password if needed for multisite
Plugin URI: https://www.scottkclark.com/
Description: WordPress 6.8 has new hashing that can be brittle with multisite. Logging into main site may upgrade the existing password but then hashing could become invalid on other sites.
Version: 1.0
Author: Scott Kingsley Clark
Author URI: https://www.scottkclark.com/

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

add_filter( 'check_password', static function ( $check, $password, $hash, $user_id ) {
	static $checking = false;

	if ( $checking || $check || empty( $user_id ) ) {
		return $check;
	}

	if ( wp_password_needs_rehash( substr( $hash, 3 ), $user_id ) ) {
		// Debug output to let you know the password hashing does not match.
		die( 'password needs rehash' );
		
		/*
		 * The below code was temporary, it does not solve the issue and actually
		 * overrides the user password regardless if the user password was correct.
		 */
		/*wp_set_password( $password, $user_id );

		$checking = true;

		$check = wp_check_password( $password, $hash, $user_id );

		$checking = false;*/
	}

	return $check;
}, 10, 4 );