이런 경우는 시퀀스가 제일 좋아 보입니다.

SQL 시퀀스 생성

http://www.dsun.kr/87

생성된 시퀀스 값을 16진수 변환 적용

https://stackoverflow.com/questions/703019/convert-integer-to-hex-and-hex-to-integer

1. 데이터 양이 많아지면서 느려진다면?
 - 인덱스 설계가 안되어 있거나?
 - (user_id + sequence_id) 인덱스가 있는지 확인하세요.
 - 인덱스가 있는데도 느리다면?
 - 쿼리를 잘못 작성한 경우입니다. 작성 쿼리를 보여주세요.
2. 16진수 변환 방법은
 

SELECT TO_CHAR(65535, 'fm000X')
     , TO_CHAR(    0, 'fm000X')
  FROM dual
;

WITH T (ID , USER_ID ) AS (
SELECT '9' ,'USER_A' FROM DUAL UNION ALL
SELECT '8' ,'USER_B' FROM DUAL UNION ALL
SELECT '7' ,'USER_C' FROM DUAL UNION ALL
SELECT '6' ,'USER_A' FROM DUAL UNION ALL
SELECT '5' ,'USER_A' FROM DUAL UNION ALL
SELECT '4' ,'USER_B' FROM DUAL UNION ALL
SELECT '3' ,'USER_C' FROM DUAL UNION ALL
SELECT '2' ,'USER_A' FROM DUAL UNION ALL
SELECT '1' ,'USER_A' FROM DUAL 
)

SELECT ID 
     , USER_ID  
     , ROW_NUMBER() OVER(PARTITION BY USER_ID ORDER BY ID ) RN
  FROM T 
 ORDER BY ID DESC

적절한 인덱스(user_id, id)가 없어서, 대체 인덱스(user_id) 만 이용하겠네요.
신규ID 에 대한 처리도 없네요? 이것도 별도 프로그램에서 처리하나보네요.
(user_id, id) 만드는것 보다는 (user_id, sequence_id)인덱스 만들고
다음과 같이 MAX 쿼리 이용하세요.

-- 숫자형 저장된 경우 --
SELECT NVL(MAX(sequence_id), 0) + 1 AS sequence_id_new
  FROM t
 WHERE user_id = #{value}
;

아. 그런데 이 쿼리는 10진수 숫자형일때 이야기 입니다.
16진수가 문자형으로 저장되어 있나요?
혹시 자리수 4자리 고정(0001)인가요? 가변자리(1)인가요?
고정자리를 사용하기를 권장합니다. 가변자리의 경우엔 MAX 로 가져오기가 어렵습니다.

가변 자리의 경우 문자열에 대함 MAX 를 가져올 수 없습니다.
또한, 초기화가 된다면? max 쿼리를 어차피 못 쓰겠네요.
인덱스를 (user_id, id, sequence_id) 로 해야겠네요.
(user_id, id, sequence_id) 보단 못하지만 (user_id, id) 도 괜찮습니다.
 

WITH t AS
(
SELECT 9 id, 'USER_A' user_id, '5' sequence_id FROM dual
UNION ALL SELECT 8, 'USER_B', '2' FROM dual
UNION ALL SELECT 7, 'USER_C', '2' FROM dual
UNION ALL SELECT 1, 'USER_D', 'FFFF' FROM dual
)
SELECT TO_CHAR(NVL(MOD(TO_NUMBER(MAX(sequence_id), 'XXXX') + 1, 65536), 0), 'fmXXXX') x
  FROM (SELECT sequence_id
             , ROW_NUMBER() OVER(ORDER BY id DESC) rn
          FROM t
         WHERE user_id = 'USER_D'
        )
 WHERE rn = 1
;

그런데
굳이 시퀀스ID를 만들어 쓰는 이유는 뭔가요?
굳이 16진수를 쓰는 이유가 뭔가요?
굳이 사이클을 돌리는 이유가 뭔가요?