SQL. Сделать проверку с EXISTS

По-хорошему, проверки такого рода возможны только для получения человеческих сообщений об ошибке на клиенте. В реальности же полагаться на exists нельзя, потому как нет никаких гарантий, что все записи будут вставляться через метод API, который вы описываете. Специально для таких ситуаций SQL предлагает вам создавать ограничения уникальности (unique constraints), описав которые, вы можете быть уверены в том, что в таблице точно всё будет хорошо:

-- на этапе создания таблицы
CREATE TABLE Client (
    Phone bigint UNIQUE,
);
-- для уже созданной таблицы
ALTER TABLE Client ADD CONSTRAINT UNIQUE (Phone);

В случае с номером телефона вам можно так же задуматься о создании уникального индекса, это, кроме вышеописанного, позволит БД быстрее выполнять запросы, если выборка будет вестись по этому полю.

CREATE UNIQUE INDEX Phone_idx ON Client(Phone);