vaya fiorella, que ingeniosa forma de localizar el próximo código a ingresar.

Sin embargo puede tornarse ineficiente si existen muchos registros en la tabla departamento, ademas segun dices, te está generando problemas de ejecución cuando la usas.
aprovechando el codigo que te dió genetix puedes obtener el proximo codigo evitando la comparación con cada codigo existente en la tabla departamentos.
sería asi:
Código SQL:
Ver originalSELECT (MAX(CAST(SUBSTRING(tabla_departamento.id_departamento, 6) AS UNSIGNED))+1) AS proximo_codigo FROM tabla_departamento;
si lo quieres de una vez concatenado con sigla (que asumo es dpto-) es asi:
Código SQL:
Ver originalSELECT concat('dpto-',(MAX(CAST(SUBSTRING(tabla_departamento.id_departamento, 6) AS UNSIGNED))+1)) AS proximo_codigo FROM tabla_departamento;
Pruebalo y nos cuentas.