Как сделать тестируемым класс, использующий нечистую встроенную функцию PHP?

Очень просто — объявить функцию необязательным параметром конструктора.

final class Service
{
    /**
     * @psalm-var callable(): int
     */
    private $time;

    /**
     * @psalm-param ?callable(): int $time
     */
    public function __construct(?callable $time = null)
    {
        $this->time = $time ?? 'time';
    }

    public function do(): void
    {
        $time = ($this->time)();
    }
}

$service = new Service();

$serviceForTesting = new Service(static fn (): int => 1234567890);

Не советую использовать либы-костыли типа php-mock/php-mock.